/**
 * 621. 任务调度器
 * https://leetcode-cn.com/problems/task-scheduler/
 */

/**
 * @param {any[]} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

const invalidCollect = { count: -Infinity, time: Infinity };

/**
 * @param {{ count: number, last: number }[]} scheduler
 * @param {number} time
 * @param {number} split
 */
function resolve(scheduler, time, split) {
  for (let i = Math.floor(scheduler.length / 2) - 1; i >= 0; i -= 1) {
    const left = i * 2 + 1;
    const right = left + 1;
    const { count: countP, last: lastP } = scheduler[i];
    const { count: countL, last: lastL } = scheduler[left];
    const { count: countR, last: lastR } = right < scheduler.length ? scheduler[right] : invalidCollect;
    const offsetP = time - lastP;
    const offsetL = time - lastL;
    const offsetR = time - lastR;
    let childIndex = -1;
    if (offsetL > split && offsetR > split) {
      if (countL > countR) {
        childIndex = left;
      } else if (countL < countR) {
        childIndex = right;
      } else if (lastL < lastR) {
        childIndex = left;
      } else {
        childIndex = right;
      }
    } else if (offsetL > split) {
      childIndex = left;
    } else if (offsetR > split) {
      childIndex = right;
    }
    if (childIndex < 0) {
      continue;
    }
    const { count: countC, last: lastC } = scheduler[childIndex];
    const offsetC = time - lastC;
    if (offsetP > split && offsetC > split) {
      if (countP > countC) {
        continue;
      }
      if (countP < countC) {
        swap(scheduler, i, childIndex);
        continue;
      }
      if (lastP < lastC) {
        continue;
      }
      swap(scheduler, i, childIndex);
      continue;
    }
    if (offsetP > split) {
      continue;
    }
    if (offsetC > split) {
      swap(scheduler, i, childIndex);
    }
  }
}

/**
 * @param {string[]} tasks
 * @param {number} n
 * @return {number}
 */
function leastInterval(tasks, n) {
  const map = new Map();
  const scheduler = [];
  for (let i = 0; i < tasks.length; i += 1) {
    const task = tasks[i];
    if (map.has(task)) {
      map.get(task).count += 1;
    } else {
      const collect = {
        // name: task,
        count: 1,
        last: -Infinity,
      };
      map.set(task, collect);
      scheduler.push(collect);
    }
  }
  map.clear();
  let leftTaskCount = tasks.length;
  let time = 0;
  // let log = '';
  while (leftTaskCount) {
    resolve(scheduler, time, n);
    const [collect] = scheduler;
    if (time - collect.last > n) {
      // log += collect.name;
      collect.last = time;
      collect.count -= 1;
      if (!collect.count) {
        scheduler.shift();
      }
      leftTaskCount -= 1;
    }
    // else {
    //   log += '-';
    // }
    time += 1;
  }
  // console.log(log);
  return time;
}

console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 2) === 8);
console.log(leastInterval(['A', 'A', 'A', 'B', 'B', 'B'], 0) === 6);
console.log(leastInterval(['A', 'A', 'A', 'A', 'A', 'A', 'B', 'C', 'D', 'E', 'F', 'G'], 2) === 16);
